2025 알고리즘 중간고사

(1) 시험시간 : 4월 21일(월요일) 오전 8시 30분 - 10시 20분

(2) 풀이 중간과정을 충분히 기술하여 채점자에게 도움이 되도록 하세요.

풀이 과정이 충분하지 않거나 최종 답만 적으면 감점됩니다.

(3) 뒷면에 답을 쓰게 되면 반드시 이 사실을 표시하기 바랍니다.

학번	이름	감독자 확인

문제 (배점)	점수	문제 (배점)	점수
1 (30)		4 (40)
2 (20)		5 (40)
3 (40)		6 (30)
		총합계 (200)

[1] 다음 재귀식의 closed form을 구하시오. 만일 그것이 불가능한 경우에는 [eqn: THETA (`)] order를 대신 구하시오. (3점)

a)  [eqn: T(`1)=```1# T(`n)=``T``(`n/2`)+`3]

b) [eqn: S(`1)=```1# S(`n)=``3S``(`n/4`)`+`n]

[2] 다음의 python code에서 call_basic() 함수의 수행 횟수를 N의 함수로 제시하시오. 그 근거를 수식을 이용하여 최대한 구체적으로 제시하시오.  답만 적으면 안 됨. (20점)

N= get_input_size( )

jump = 1

while( jump < N  ) :

jump += 1

S= 0

while( S < N  ) :

S += jump

call_basic( )

[eqn: T(N) & =`N`+`` LEFT ⌈ {N} over {2} RIGHT ⌉ + LEFT ⌈ {N} over {3} RIGHT ⌉ + LEFT ⌈ {N} over {4} RIGHT ⌉ `+ CDOTS LEFT ⌈ {N} over {N-1} RIGHT ⌉ + LEFT ⌈ {N} over {N} RIGHT ⌉ `# & LEQ =`N`+` {N`} over {2} + {N`} over {3} CDOTS CDOTS {N`} over {N-1} + {N`} over {N} +N# & =N`cdot`log _{e} `N+N# & =N(``log _{e} `N+1) # &= Theta(N ```log N ``)]

[3] N개의 금화(동전)가 있다. 이 중 진품과 달리 약간 가벼운 가짜 금화가 1개 포함되어 있다. 이 가짜 동전을 옆 그림과 같은 양팔 저울만을 이용해서 찾으려고 한다.

a) N=5일 때 worst case 기준으로 한번의 저울질로 가짜를 찾을 수 없음을 보이시오. 즉 그 lower bound가 2임을 증명하시오. (1번으로는 불가능이므로 적어도 2번 이상은 필요하다는 말) [10점]

b) N=6일 때 Worst Case 기준으로 optimal algorithm을 decision tree로 그리고 자신이 제시한 트리 기준으로 저울질의 최악, 최선, 평균을 각각 계산하시오. [10점]

c)  N=32개의 금화가 준비되어 있다. 우리는 이 중에서 약간 가벼운 가짜 동전이 1개, 혹은 최대 2개가 있음을 이미 알고 있다. 우리는 양팔 저울을 이용해서 가짜가 1개인지, 또는 2개인지를 확인하려고 한다. 이를 위한 최적의 저울질은 몇 번이 필요한지 decision tree를 그려서 제시하시오. 단 가짜가 어떤 동전 [eqn: c _{i}]인지는 특정할(specify) 필요가 없다. 오직 가짜의 개수가 1개인지, 2개인지만 확인하면 된다. [20점]

8개씩 4개의 묶음 A, B, C, D를 만들어 A|B, C|D를 측정

A | B	C | D	가짜의 갯수
=	=	2개 , AB 혹은 CD에 각각 한 개씩 존재함
=	<	내려간 8쪽을 다시 2개씩 4개로 비교, 추가 2회 더하여 확인 가능
<	=	내려간 8쪽을 다시 2개씩 4개로비교 추가 2회 더하여 확인 가능
<	<	2개, AB, CD에 각각 1개씩 존재

8개에서 가짜가 1개인지 2개인지는 확인해야 함.

8개 동전에서 가짜의 갯수를 1개, 2개를 확인하는 경우에는 최악의 경우 3번이 필요합니다.

4 : 4 해서 같으면 가짜 2개

한쪽이 내려가면 그 4개를 다시 2:2로 비교

같으면 가짜 2개. 한쪽이 내려가면 다시 내려간 쪽으로 비교

무게가 같으면 가짜는 2개, 한쪽만 내려가면 1개

따라서 정답은 worst case로 5번입니다. 또는 16:16, 8:8, 4:4, 2:2 1:1로 비교해도

가능합니다.

[4] 다음은 5개의 vertex로 구성된 방향 그래프(directed graph)이다. 이 그래프에서 Floyd-Warshall 알고리즘으로 모든 쌍 간의 shortest path를 구하려고 한다.

[eqn: D ^{(k)}[i][j]]는 두 정점 [eqn: i]에서 [eqn: j]로 가는 최단경로 중 중간에 지나갈 수 있도록 허락되는 노드의 index가 최대 [eqn: k]인 경로의 거리로 정의된다. 따라서 [eqn: D ^{(0)} [i][j]]는 두 정점 [eqn: i,j]의 edge 길이를 의미한다. 이것을 이용해서 우리는 최종적으로 [eqn: D ^{(5)} [i][j]]를 구하면 결국 모든 쌍 [eqn: (i,j)]의 최단거리를 구하게 된다. 여러분은 [eqn: D ^{(0)} [i][j]]를 바탕으로 [eqn: D ^{(1)} [i][j]], [eqn: D ^{(2)} [i][j]]를 채워 넣으시오.

(a) [eqn: D ^{(k)}[i][j]]를 위한 dynamic programming 식을 제시하시오. [10점]

(b) 아래 그래프를 기준으로 [eqn: D ^{(k)}[i][j]], [eqn: k=0,1,2]를 채워 완성하시오.[30점]

[eqn: D ^{(0)} [i][j]]

	1	2	3	4	5
1	0	5	-	-	-
2	-	0	7	2	7
3	8	4	0	-	-
4	15	-	10	0	12
5	2	-	-	-	0

[eqn: D ^{(1)} [i][j]]                                    [eqn: D ^{(2)} [i][j]]

	1	2	3	4	5
1	0	5	-	-	-
2	-	0	7	2	7
3	8	4	0	-	-
4	15	20	10	0	12
5	2	7	-	-	0

	1	2	3	4	5
1	0
2		0
3			0
4				0
5					0

[5] 방학에 유럽 여행으로 베를린(Berlin)을 간다. 이 도시에서는 관광객을 위하여 3종류의 교통카드를 제공하다. 각각은 1일권(E), 3일권(D), 5일권(F)으로 이 기간 동안에는 무제한으로 승하차가 가능하다. E, D, F ticket의 가격(euro)은  각각 10, 19, 27 이다. 여러분에게는 [eqn: d]일의 일정 동안 교통편을 사용해야하는 일(day)가 이미 결정되어 있다. 이 일정 동안 가장 적은 비용으로 지정한 날의 교통편을 모두 사용하는 최적의 일정을 작성하시오. (아래 표에서 T(our)가 사용하는 날이다.

Ein(1), Drei(3), Fünf(5)

a) C[i]는 1일부터 [eqn: i]일까지의 교통편을 이용하는 최저 ticket 비용을 나타낸다고 할 때 [eqn: C[i]] 계산을 위한 Dynamic programming 식을 제시하시오. 10점]

b)  [5점]   E=10,  D=19, F=27

Day	1	2	3	4	5	6
Tour	T		T	T		T
cost

c) [10점]

Day	1	2	3	4	5	6	7	8	9	10
Tour		T	T		T	T	T		T	T
cost

d) [eqn: i=10]번까지는 b)와 같으므로 앞의 결과를 활용하면 된다. [15점]

Day	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Tour		T	T		T	T	T		T	T		T		T	T
cost

[6]   크기가 다른 2개의 큰 파일 A, B 에 데이터가 저장되어 있다. A에 담긴 원소의 개수는 [eqn: n ^{2}]이며 다른 B에는 [eqn: n]개의 원소가 순서없이 저장되어 있다. 우리는 이 두 파일 A, B에 공통으로 존재하는 원소가 있는지만을 확인하려고 한다. 즉 [eqn: A cap B = EMPTYSET] 인지를 판단하려고 한다. 이 작업을 worst case 기준으로 최적인 알고리즘을 그 복잡도와 함께 제시하시오. 단 알고리즘은 pseudo 코드로 제시하면 된다. (한글 명령어도 가능).

만일 가장 “단순-무식”하게 접근한다면 A의 모든 원소를 B의 모든 원소와 비교하는 것이므로 그 복잡도는 [eqn: THETA (n ^{2} `` {cdot{``}} n`)]= [eqn: Theta(n^3``)]이 된다. 여러분은 이 [eqn: THETA `(`n ^{3`} )]인 단순-무식 알고리즘보다 asymptotic 기준으로 더 나은 복잡도의 알고리즘을 제시해야 한다.

(a) [eqn: vert A`` vert `=`n ^{2}] , [eqn: vert `B``` vert `=`n], 두 파일의 초기 상태는 unsorted일 때를 가정하고 이 문제를 해결하시오. 단 이 과정에서 여러분은 필요할 때 배열 L을 정렬하는 내장 함수 sort( L )을 사용할 수 있으며 이 정렬 알고리즘의 복잡도는 L에 포함된 원소의 개수가 [eqn: m]일 때 [eqn: THETA ` ( m ``log ``m )]로 가능하다고 가정한다. [20점]

(b) [eqn: vert A`` vert `=`n ^{2}] , [eqn: vert `B``` vert `=`n], 인 두 파일이 이미 sorting된 상태로 제공될 때 상태에서 이 문제, 즉 boolean([eqn: A CAP B]) 를 해결하시오.